class Solution {
public:
    const int INF=0x3f3f3f3f;
    void Bellman_Ford(vector<vector<int>> &graph, int n)
    {
        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
            {
                if(i==k||graph[i][k]==INF) continue; //优化
                for(int j=1; j<=n; j++)
                {
                    // if(i==j||graph[k][j]==INF) continue;
                    graph[i][j]=min(graph[i][k]+graph[k][j], graph[i][j]);
                }
            }
    }

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<int>> graph(n+1, vector<int>(n+1, INF));
        for(auto &e:times)
            graph[e[0]][e[1]]=e[2];
        Bellman_Ford(graph, n);
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            if(i==k) continue;
            ans=max(ans, graph[k][i]);
        }
        return ans==INF?-1:ans;
    }
};